package leetcode_题库;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/29 10:07 星期一
 */
public class _701_二叉搜索树中的插入操作 {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        return dfs(root, val);
    }
    /**
     * > 2022/08/29 10:14:37
     * 解答成功:
     * 	执行耗时:0 ms,击败了100.00% 的Java用户
     * 	内存消耗:42.4 MB,击败了16.66% 的Java用户
     * @param n
     * @param val
     * @return
     */
    public TreeNode dfs(TreeNode n, int val) {
        if (n == null) {
            //空，插入一个新结点即可
            return new TreeNode(val);
        }
        //二叉树规律，小就左结点，大就右结点
        if (n.val > val) {
            n.left = dfs(n.left, val);
        } else {
            n.right = dfs(n.right, val);
        }
        return n;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
